package demo14;

import java.util.ArrayList;
import java.util.List;

/**
 * 找出所有子集的异或总和再求和
 * https://leetcode.cn/problems/sum-of-all-subset-xor-totals/
 */
class Solution1 {
    List<Integer> path = new ArrayList<>();
    int ret;
    int len;
    public int subsetXORSum(int[] nums) {
        len = nums.length;
        dfs(nums,0);
        return ret;
    }

    private void dfs(int[] nums, int pow) {
        int count = 0;
        for(int num : path) {
            count ^= num;
        }
        ret += count;

        for(int i = pow; i < len; i++) {
            path.add(nums[i]);
            dfs(nums,i+1);
            // 恢复现场
            path.remove(path.size() -1);
        }
    }
}